Tú Xuất là con một đốc học Hà Nội, gốc ở Thanh Hóa hoặc Nghệ An, thường trú ở xã Phương Trung, huyện Thanh Oai, tỉnh Hà Đông xưa (nay thuộc Hà Nội), đến Tú Xuất là đời thứ tư. Tú Xuất cũng thuộc dòng họ Nguyễn Đình ông là con trai trưởng của Nguyễn Đình Lập người đỗ cử nhân năm Gia Long thứ 12 (1812), là đốc học Hà Nội, có thời gian ông đã làm đốc học lục tỉnh, là giám khảo khoa thi hương ở Nghệ An. Họ Nguyễn Đình có ba chi, Tú Xuất thuộc chi thứ ba.[6]

Ông nội Tú Xuất là Nguyễn Đình Linh. Đối với Tú Xuất, ông có học hành lăn lộn nhiều năm với khoa cử. Thông minh, tri thức hơn người, nhưng năm lần qua trường thi hương, ông vẫn không vượt qua được vũ môn để thành ông nghè, ông cống. Thế là một lần nữa trên đất Hà Thành lại rộ lên các chuyện mà mọi người cho là "táo trời" là "bạo thiên nghịch địa", dân chúng thì nhiều người khen và cảm phục. Cuối đời không ai rõ về ông, có người nói Tú Xuất vì tham gia trong đội quân Tam Đường chống Pháp nhưng thất bại nên ông lánh nạn và mất tích từ đó.[7]